#!/usr/bin/env python3

"""
Merge k sorted linked lists and return it as one sorted list. 
"""

class MinHeap:
    def __init__(self, num):
        self.array = [None] * num
        self.current_size = 0

    def insert(self, key, value):
        current = self.current_size
        self.current_size += 1
        self.array[current] = (key, value)
        while current != 0:
            parent_index = self.parent_index_of_i(current)
            parent_val = self.array[parent_index]
            if parent_val[0] > key:
                self.array[current], self.array[parent_index] = parent_val, (key, value)
                current = parent_index
            else:
                break
        
    def min(self):
        result = self.array[0] if self.current_size > 0 else None
        if self.current_size > 1:
            self.array[0], self.array[self.current_size - 1] = self.array[self.current_size - 1], None
        self.current_size -= 1
        if self.current_size <= 1:
            return result

        current = 0
        current_val = self.array[0]
        while current < self.current_size:
            left_index = self.left_child_index(current)
            right_index = self.right_child_index(current)
            if right_index < self.current_size:
                # left and right all exist
                left = self.array[left_index]
                right = self.array[right_index]
                if left[0] < current_val[0] and right[0] >= left[0]:
                    self.array[current], self.array[left_index] = left, current_val
                    current = left_index
                elif right[0] < current_val[0] and right[0] < left[0]:
                    self.array[current], self.array[right_index] = right, current_val
                    current = right_index
                else:
                    break
            elif left_index < self.current_size:
                left = self.array[left_index]
                if left[0] < current_val[0]:
                    self.array[current], self.array[left_index] = left, current_val
                    current = left_index
                else:
                    break
            else:
                break
        return result
                    

    def parent_index_of_i(self, index):
        return int((index - 1) / 2)

    def left_child_index(self, index):
        return 2 * index + 1

    def right_child_index(self, index):
        return 2 * index + 2
class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

    def link(self, next):
        self.next = next
        return next

    def show(self):
        print(self.val, end=' ')
        if self.next:
            self.next.show()

class Solution:
    def merge_k_lists(self, lists):
        head = [None] * len(lists)
        heap = MinHeap(len(lists))
        for index, val in enumerate(lists):
            if val:
                heap.insert(val.val, (index, val))
                head[index] = val.next
        result = None
        current = None
        while True:
            min_node = heap.min()
            if min_node is None:
                break
            if result is None:
                result = current = min_node[1][1]
            else:
                current.next = min_node[1][1]
                current = current.next
            index = min_node[1][0]
            source = head[index]
            if source is None:
                continue
            heap.insert(source.val, (index, source))
            head[index] = source.next
        return result

if __name__ == '__main__':
    input_array = [[-8,-7,-7,-5,1,1,3,4],[-2],[-10,-10,-7,0,1,3],[2]]
    input_array = [[-8,-7,-6,-3,-2,-2,0,3],[-10,-6,-4,-4,-4,-2,-1,4],[-10,-9,-8,-8,-6],[-10,0,4]]
    input_args = []
    for list_node in input_array:
        current = None
        for node in list_node:
            if current is None:
                current = ListNode(node)
                input_args.append(current)
            else:
                current.next = ListNode(node)
                current = current.next
                

    solution = Solution()
    result = solution.merge_k_lists(input_args)
    result.show()
    print()
